﻿#include <iostream>

using namespace std;

void printfArray(int *array, int length) {
    for (int i = 0; i < length; ++i) {
        cout << array[i] << " ";
    }
    cout << endl;
}

void countSort(int *array, int length) {
    int minValue;
    int maxValue;

    bool flag = true;
    for (int i = 0; i < length; ++i) {
        int value = array[i];
        if (flag) {
            minValue = maxValue = value;
            flag = false;
        } else {
            minValue = min(minValue, value);
            maxValue = max(maxValue, value);
        }
    }

    int *temp = (int *) malloc(sizeof(int) * (maxValue - minValue + 1));
    for (int i = 0; i < length; i++) {
        temp[array[i] - minValue]++;
    }

    int count = 0;
    for (int i = minValue; i <= maxValue; ++i) {
        for (int j = 0; j < temp[i - minValue]; j++) {
            array[count++] = i;
        }
    }

    free(temp);
}


int main() {
    int array[] = {2, 4, 6, 7, 3, 2, 5, 6, 7, 2, 2, 4, 2, 1, 4, 1, 6, 7, 9, 0, 8};
    int length = (sizeof(array) / sizeof(int));
    cout << "length = " << length << endl;

    cout << "排序前: ";
    printfArray(array, length);

    countSort(array, length);

    cout << "排序后: ";
    printfArray(array, length);

    return 0;
}
